package com.cat.graphTheory;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/is-graph-bipartite/
 * @create 2025/10/11 20:41
 * @since JDK17
 */

public class Solution43 {
    boolean ok = true;
    boolean[] vis, color;
    void dfs(int[][] g, int cur) {
        if (!ok) {
            return;
        }
        vis[cur] = true;    // 标记已经被遍历了
        for (int next : g[cur]) {
            if (!vis[next]) {   // 没有便遍历过
                color[next] = !color[cur];  // 染色
                dfs(g, next);
            } else {    // 该节点已经被遍历过，检查上一个节点是否被遍历过
                if (color[next] == color[cur]) {    // 染色失败
                    ok = false;
                }
            }
        }

    }

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        vis = new boolean[n];
        color = new boolean[n];
        for (int i = 0; i < n; i++) {
            dfs(graph, i);
        }

        return ok;
    }
}
